The present invention generally relates to improving the computational speed of a computer algorithm. The present invention has particular applicability in the area of cryptographic algorithms, including Rivest, Shamir and Adleman (“RSA”) encryption algorithms.
Cryptographic systems are ubiquitous in today's computer-driven society. Such systems are used to provide secure communications.
Public-key cryptography, and the widely-used RSA encryption technique in particular, is increasingly important to data security these days. As discussed in greater detail hereinafter, public-key cryptography (RSA as a worldwide standard) generally provides the means for two remote parties to share information without transmitting a code (a “key”) that a would-be eavesdropper could use to break the encryption. RSA has withstood about 20 years of cryptoanalysis (breaking ciphertext—that is, recovering plaintext without knowing the key).
Most of today's cryptographic schemes involve symmetric (secret) key algorithms or asymmetric (public) key algorithms.
In symmetric-key cryptographic systems, the sender of information uses the same key to encrypt the information that the recipient of the information uses to decrypt it (that is, the same key is used to encode and decode information). The encoding procedure consists of a sequence of actions on the source data using the key, the decoding procedure uses the same key to perform the reverse actions on the encoded information. Symmetric-key systems require that each sender and recipient exchange the shared key in a secure manner. To decode the encoded information without the shared key is ostensibly impossible.
Compared to public-key algorithms, symmetric-key algorithms are very fast. For this reason, symmetric-key encryption is preferred for encrypting large amounts of data.
However, problems arise if information encoded using the symmetric-key approach is transmitted via an ordinary non-secure channel. Because both the sender and the recipient must have the same key, it becomes necessary to employ an additional secure channel to transmit the key. As a result, the system becomes fragile and administrative complications arise.
DES is a symmetric-key algorithm that, historically, has been widely used but that, recently, has become obsolete due to its vulnerability. On or about October, 2000, NIST announced that Rijndael had been selected as the proposed AES, and underwent the process of being made the official standard. Today, Rijndael is considered to be the most commonly used symmetric-key algorithm.
The idea of public-key cryptography (asymmetric algorithm) was introduced in 1976 by Whitfield Diffie and Martin Hellman in order to solve the key management problem. In their concept, each person holds a pair of keys—one a public key and the other a private key. Each public key is published while the private key is kept secret. The sender encrypts information using the public key of the recipient; the recipient uses the private key for decrypting the encrypted information.
The need for the sender and recipient to share secret information is eliminated in public-key cryptographic systems as all communications involve only public keys and no private key is ever transmitted or shared. The potential problem associated with symmetric-key systems that an unauthorized party will intercept the secret key is avoided.
A requirement of public-key systems is that public keys are associated with their users in a trusted (authenticated) manner (for instance, in a trusted directory). Anyone can send a confidential message by just using public information, but the message can be decrypted only with a private key, which is in the sole possession of the intended recipient. Furthermore, public-key cryptography can be used not only for privacy (encryption), but also for authentication (digital signatures).
RSA is a public-key system used for both encryption and authentication purposes. As is understood by those of ordinary skill in the cryptographic arts, RSA works as follows: take two large primes, p and q, and find their product n=pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p−1)(q−1), which means that e and (p−1)(q−1) have no common factors except 1. Find another number d such that (ed−1) is divisible by (p−1)(q−1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n,e); the private key is (n,d). The factors p and q may be kept with the private key or destroyed.
By way of example, suppose that Alice wants to send a message m to Bob using RSA encryption. Alice creates the cipher text c by exponentiating: c=me mod n, where e and n are Bob's public key. Alice sends c to Bob. To decrypt, Bob exponentiates: m=cd mod n; the relationship between e and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt message m.
As another example of RSA in the context of authentication, suppose that Alice wants to send a message m to Bob in such a way that Bob is assured that the message is authentic and is from Alice. Alice creates a digital signature s by exponentiating: s=md mod n, where d and n are Alice's private key. Alice sends m and s to Bob. To verify the signature, Bob exponentiates and checks that the message m is recovered: m=se mod n, where e and n are Alice's public key.
A disadvantage of public-key cryptographic systems in general is that they require large amounts of computer processing power, and, as a consequence, are slow. It therefore comes as no surprise that the biggest obstacle (disadvantage) with RSA is its low speed (which is directly attributable to the fact that the RSA public-key algorithm requires large amounts of computer processing power).
Recognizing that public-key encryption algorithms such as RSA are computationally intensive, some conventional encryption systems provide users with the capability to use public-key encryption to securely exchange a shared symmetric key. However, such hybrid approaches have their associated disadvantages, and there remains a need for a faster public-key encryption algorithm (e.g., a faster RSA algorithm).
The present invention satisfies the foregoing need for faster computer algorithms by providing a technique for accelerating the computational speed of a computer algorithm, such as, for example, a cryptographic algorithm (e.g., an RSA algorithm), without affecting the underlying nature of the algorithm—i.e., the way the algorithm works and the results generated thereby.
It will be appreciated that, in addition to the acceleration of encryption algorithms, the present invention has applicability with respect to video compression algorithms, motion detection and compression algorithms, optical character recognition (“OCR”) algorithms, audio compression algorithms, digital photography zooming applications, and other algorithms/applications where acceleration of computational speed is desirable.